Почему обработка отсортированного массива выполняется быстрее, чем обработка несортированного массива?

Вы стали жертвой неудачного предсказания ветвления.
Что такое прогнозирование ветвей?
Рассмотрим железнодорожный узел:
Изображение Mecanismo, через Wikimedia Commons. Используется по лицензии CC-By-SA 3.0.
Теперь для аргументации предположим, что это было в 1800-х годах - до дальней связи или радиосвязи.
Вы управляете перекрестком и слышите приближающийся поезд. Вы не представляете, по какому пути он должен идти. Вы останавливаете поезд, чтобы спросить машиниста, в каком направлении они хотят. Затем вы устанавливаете переключатель соответствующим образом.
Поезда тяжелые и обладают большой инерцией. Таким образом, они запускаются и замедляются бесконечно.
Есть ли способ лучше? Вы угадаете, в каком направлении пойдет поезд!
Если вы угадали, это продолжается.
Если вы ошиблись, капитан остановится, отступит и крикнет вам, чтобы вы щелкнули выключателем. Затем он может перезапуститься по другому пути.
Если вы каждый раз угадаете, поезд никогда не остановится. Если вы слишком часто угадаете неправильно, поезд будет много времени останавливаться, двигаться назад и перезагружаться.
Рассмотрим оператор if: на уровне процессора это инструкция ветвления:
Вы процессор и видите ветку. Вы не представляете, в каком направлении это пойдет. Чем ты занимаешься? Вы останавливаете выполнение и ждете, пока не будут выполнены предыдущие инструкции. Затем вы продолжаете идти по правильному пути.
Современные процессоры сложны и имеют длинные конвейеры. Так что им нужна вечность, чтобы «разогреться» и «замедлиться».
Есть ли способ лучше? Вы угадаете, в каком направлении пойдет ветка!
Если вы угадали, вы продолжаете выполнение.
Если вы не угадали, нужно промыть трубопровод и откатиться на ветку. Затем вы можете начать с другого пути.
Если вы каждый раз угадаете правильно, казнь никогда не прекратится. Если вы слишком часто ошибаетесь, вы тратите много времени на откатывание, откат и перезапуск.
Это предсказание ветвления. Я признаю, что это не лучшая аналогия, поскольку поезд мог просто сигнализировать о направлении флагом. Но в компьютерах процессор до последнего момента не знает, в каком направлении пойдет ветвь.
Итак, как бы вы стратегически догадывались, чтобы минимизировать количество раз, когда поезд должен возвращаться назад и спускаться по другому пути? Вы посмотрите на прошлую историю! Если поезд идет налево в 99% случаев, значит, вы угадали. Если он чередуется, то вы меняете свои догадки. Если каждые три раза он идет в одну сторону, вы угадаете то же самое ...
Другими словами, вы пытаетесь определить шаблон и следовать ему. Примерно так работают предикторы ветвления.
У большинства приложений есть ветки с хорошим поведением. Таким образом, современные предсказатели ветвления обычно достигают> 90% попаданий. Но когда вы сталкиваетесь с непредсказуемыми ветвлениями без распознаваемых шаблонов, предсказатели ветвлений практически бесполезны.
Дополнительная литература: статья «Предсказатель ветвления» в Википедии.
Как указано выше, виноват следующий оператор if:
если (data [c]> = 128)
сумма + = данные [c];
Обратите внимание, что данные равномерно распределяются между 0 и 255. Когда данные сортируются, примерно первая половина итераций не входит в if-оператор. После этого все они войдут в if-оператор.
Это очень удобно для предсказателя ветвления, поскольку ветвление последовательно проходит в одном и том же направлении много раз. Даже простой счетчик насыщения правильно предсказывает ветвь, за исключением нескольких итераций после смены направления.
Быстрая визуализация:
T = ветвь взята
N = ветвь не занята
data [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
ветвь = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (легко предсказать)
Однако, когда данные полностью случайны, предсказатель ветвления оказывается бесполезным, потому что он не может предсказать случайные данные. Таким образом, вероятно, будет около 50% ошибочных прогнозов (не лучше, чем случайное предположение).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
ветвь = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (полностью случайно - трудно предсказать)
Так что же можно сделать?
Если компилятор не может оптимизировать ветвь до условного перехода, вы можете попробовать несколько хаков, если вы готовы пожертвовать удобочитаемостью ради производительности.
Заменить:
если (data [c]> = 128)
сумма + = данные [c];
с участием:
int t = (данные [c] - 128) >> 31;
сумма + = ~ t & данные [c];
Это устраняет ветвление и заменяет его некоторыми поразрядными операциями.
(Обратите внимание, что этот прием не является строго эквивалентным исходному оператору if. Но в данном случае он действителен для всех входных значений data [].)
Тесты: Core i7 920 @ 3,5 ГГц
C ++ - Visual Studio 2010 - выпуск x64
// Ветка - случайная
секунд = 11,777
// Ветка - Сортировка
секунды = 2,352
// Без ветвей - случайный
секунды = 2,564
// Без филиалов - Сортировка
секунды = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Ветка - случайная
секунд = 10,93293813
// Ветка - Сортировка
секунд = 5,643797077
// Без отделения -Случайный
секунды = 3,113581453
// Без филиалов - Сортировка
секунды = 3,186068823
Наблюдения:
С веткой: существует огромная разница между отсортированными и несортированными данными.
Хакерство: нет разницы между отсортированными и несортированными данными.
В случае C ++ взлом выполняется немного медленнее, чем с ветвью, когда данные сортируются.
Общее практическое правило - избегать зависимых от данных ветвлений в критических циклах (например, в этом примере).
Обновить:
GCC 4.6.1 с -O3 или -ftree-vectorize на x64 может генерировать условный ход. Таким образом, нет никакой разницы между отсортированными и несортированными данными - оба работают быстро.
(Или несколько быстро: для уже отсортированного случая cmov может быть медленнее, особенно если GCC помещает его на критический путь, а не просто добавляет, особенно на Intel до Broadwell, где cmov имеет задержку в 2 цикла: флаг оптимизации gcc -O3 делает код медленнее чем -O2)
VC ++ 2010 не может генерировать условные перемещения для этой ветки даже в / Ox.
Компилятор Intel C ++ (ICC) 11 творит чудеса. Он меняет местами две петли, тем самым поднимая непредсказуемую ветвь во внешний цикл. Таким образом, он не только невосприимчив к ошибочным предсказаниям, но и в два раза быстрее, чем все, что может генерировать VC ++ и GCC! Другими словами, ICC воспользовалась тестовым циклом, чтобы победить тест ...
Если вы дадите компилятору Intel код без ветвей, он просто векторизует его вправо ... и будет так же быстро, как и с ветвью (с заменой цикла).
Это говорит о том, что даже зрелые современные компиляторы могут сильно различаться по своей способности оптимизировать код ...
|
Прогнозирование ветвления.
В отсортированном массиве условие data [c]> = 128 сначала ложно для серии значений, затем становится истинным для всех последующих значений. Это легко предсказать. С несортированным массивом вы платите за разветвление.
|
Причина, по которой производительность резко улучшается при сортировке данных, заключается в том, что штраф за предсказание ветвления удаляется, как красиво объяснено в ответе Mysticial.
Теперь, если мы посмотрим на код
если (data [c]> = 128)
сумма + = данные [c];
мы можем обнаружить, что смысл этой конкретной ветки if ... else ... состоит в том, чтобы добавить что-то, когда условие выполнено. Этот тип ветвления может быть легко преобразован в оператор условного перемещения, который будет скомпилирован в инструкцию условного перемещения: cmovl в системе x86. Ветвление и, следовательно, потенциальный штраф за предсказание ветвления удаляются.
В C, то есть в C ++, оператор, который будет компилироваться напрямую (без какой-либо оптимизации) в инструкцию условного перемещения в x86, является тернарным оператором ...? ...: .... Итак, мы переписываем приведенное выше утверждение в эквивалентное:
сумма + = данные [c]> = 128? data [c]: 0;
Сохраняя читабельность, мы можем проверить коэффициент ускорения.
На процессоре Intel Core i7-2600K @ 3,4 ГГц и в режиме выпуска Visual Studio 2010 эталонный тест (формат скопирован из Mysticial):
x86
// Ветка - случайная
секунды = 8,885
// Ветка - Сортировка
секунды = 1,528
// Без ветвей - случайный
секунды = 3,716
// Без филиалов - Сортировка
секунды = 3,71
x64
// Ветка - случайная
секунд = 11.302
// Ветка - Сортировка
секунд = 1,830
// Без ветвей - случайный
секунды = 2,736
// Без филиалов - Сортировка
секунды = 2,737
Результат устойчив в нескольких тестах. Мы получаем большое ускорение, когда результат перехода непредсказуем, но мы немного страдаем, когда он предсказуем. Фактически, при использовании условного перемещения производительность одинакова независимо от шаблона данных.
Теперь давайте посмотрим внимательнее, исследуя создаваемую ими сборку x86. Для простоты мы используем две функции max1 и max2.
max1 использует условную ветвь if ... else ...:
int max1 (int a, int b) {
если (а> б)
вернуть;
еще
return b;
}
max2 использует тернарный оператор ...? ...: ...:
int max2 (int a, int b) {
вернуть a> b? а: б;
}
На машине x86-64 GCC -S генерирует сборку ниже.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
уехать
Ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
уехать
Ret
max2 использует гораздо меньше кода из-за использования инструкции cmovge. Но реальный выигрыш заключается в том, что max2 не включает переходов по ветвям, jmp, что значительно снизит производительность, если прогнозируемый результат неверен.
Так почему же условный ход работает лучше?
В типичном процессоре x86 выполнение инструкции разделено на несколько этапов. Грубо говоря, у нас разное оборудование для разных этапов. Таким образом, нам не нужно ждать завершения одной инструкции, чтобы начать новую. Это называется конвейерной обработкой.
В случае ветвления следующая инструкция определяется предыдущей, поэтому мы не можем выполнять конвейерную обработку. Приходится либо ждать, либо предсказывать.
В случае условного перемещениякоманда условного перемещения выполнения делится на несколько этапов, но более ранние этапы, такие как выборка и декодирование, не зависят от результата предыдущей инструкции; результат нужен только на последних этапах. Таким образом, мы ждем долю времени выполнения одной инструкции. Вот почему версия с условным перемещением медленнее, чем ветвление, когда прогнозирование выполняется легко.
Книга «Компьютерные системы: взгляд программиста», второе издание, подробно объясняет это. Вы можете проверить раздел 3.6.6 для инструкций условного перемещения, всю главу 4 об архитектуре процессора и раздел 5.11.2 для специальной обработки штрафов за предсказание переходов и ошибочное предсказание.
Иногда некоторые современные компиляторы могут оптимизировать наш код для сборки с лучшей производительностью, иногда некоторые компиляторы не могут (рассматриваемый код использует собственный компилятор Visual Studio). Знание разницы в производительности между ветвлением и условным перемещением, когда оно непредсказуемо, может помочь нам написать код с более высокой производительностью, когда сценарий становится настолько сложным, что компилятор не может оптимизировать их автоматически.
|
Если вам интересно, какие еще оптимизации можно сделать с этим кодом, подумайте об этом:
Начиная с исходного цикла:
for (беззнаковый i = 0; i <100000; ++ i)
{
for (без знака j = 0; j  = 128)
сумма + = данные [j];
}
}
С заменой цикла мы можем смело изменить этот цикл на:
for (без знака j = 0; j  = 128)
сумма + = данные [j];
}
}
Затем вы можете видеть, что условное выражение if остается постоянным на протяжении всего выполнения цикла i, поэтому вы можете поднять if out:
for (без знака j = 0; j  = 128)
{
for (беззнаковый i = 0; i <100000; ++ i)
{
сумма + = данные [j];
}
}
}
Затем вы видите, что внутренний цикл может быть свернут в одно выражение, если модель с плавающей запятой позволяет это (например, / fp: fast)
for (без знака j = 0; j  = 128)
{
сумма + = данные [j] * 100000;
}
}
Этот в 100 000 раз быстрее, чем раньше.
|
Несомненно, некоторые из нас будут заинтересованы в способах идентификации кода, который проблематичен для предсказателя ветвления ЦП. Инструмент cachegrind Valgrind имеет симулятор предсказателя ветвления, который включается с помощью флага --branch-sim = yes. Выполнение его по примерам в этом вопросе с уменьшением количества внешних циклов до 10000 и компиляцией с g ++ дает следующие результаты:
Сортировано:
== 32551 == Филиалы: 656,645,130 (656,609,208 усл. + 35,922 инд.)
== 32551 == Ошибочные прогнозы: 169,556 (169,095 усл. + 461 инд.)
== 32551 == Скорость неверного прогноза: 0,0% (0,0% + 1,2%)
Несортированный:
== 32555 == Филиалы: 655,996,082 (655,960,160 усл. + 35,922 инд.)
== 32555 == Ошибочные прогнозы: 164 073 152 (164 072 692 усл. + 460 инд.)
== 32555 == Скорость неверного прогноза: 25,0% (25,0% + 1,2%)
Переходя к построчному выводу, производимому cg_annotate, мы видим для рассматриваемого цикла:
Сортировано:
Bc Bcm Би Бим
10,001 4 0 0 для (без знака i = 0; i <10000; ++ i)
. . . . {
. . . . // основной цикл
327,690,000 10,016 0 0 для (без знака c = 0; c  = 128)
0 0 0 0 сумма + = данные [c];
. . . . }
. . . . }
Несортированный:
Bc Bcm Би Бим
10,001 4 0 0 для (беззнаковый i = 0; i <10000; ++ i)
. . . . {
. . . . // основной цикл
327,690,000 10,038 0 0 для (без знака c = 0; c  = 128)
0 0 0 0 сумма + = данные [c];
. . . . }
. . . . }
Это позволяет легко идентифицировать проблемную строку - в несортированной версии строка if (data [c]> = 128) вызывает 164 050 007 неверно предсказанных условных переходов (Bcm) в модели предсказателя ветвления cachegrind, тогда как в отсортированной версии она вызывает только 10 006. .
В качестве альтернативы в Linux вы можете использовать подсистему счетчиков производительности для выполнения той же задачи, но с собственной производительностью с использованием счетчиков ЦП.
перф. стат ./sumtest_sorted
Сортировано:
Статистика счетчика производительности для './sumtest_sorted':
11808.095776 частота задач # 0,998 Используемые процессоры
1062 переключателя контекста # 0,090 К / с
14 CPU-миграций # 0.001 К / сек
337 ошибок страницы # 0,029 К / сек
26 487 882 764 цикла # 2,243 ГГц
41025654322 инструкции # 1,55 инсн за цикл
6,558,871,379 веток # 555,455 М / сек
567 204 пропуска филиалов # 0,01% всех филиалов
Прошло 11,827228330 секунд
Несортированный:
Производительностьстатистика счетчика для './sumtest_unsorted':
28877.954344 частота задач # 0,998 Используемые ЦП
2584 переключателя контекста # 0,089 К / с
18 CPU-миграций # 0.001 К / сек
335 ошибок страницы # 0,012 К / сек
65 076 127 595 циклов # 2,253 ГГц
41032528741 инструкция # 0,63 инсн за цикл
6 560 579 013 веток # 227,183 М / сек
1 646 394 749 филиалов # 25,10% всех филиалов
Прошло 28,935500947 секунд
Он также может выполнять аннотацию исходного кода с разборкой.
perf record -e пропуски веток ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Процент | Исходный код и разборка sumtest_unsorted
------------------------------------------------
...
: сумма + = данные [c];
0.00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4.60: 400a26: cltq
0.00: 400a28: добавить% rax, -0x30 (% rbp)
...
Подробнее см. В руководстве по производительности.
|
Я только что прочитал этот вопрос и ответы на него и чувствую, что ответа нет.
Распространенный способ устранения предсказания ветвления, который, как я обнаружил, особенно хорошо работает в управляемых языках, - это поиск по таблице вместо использования ветки (хотя я не тестировал его в этом случае).
Этот подход в целом работает, если:
это небольшая таблица, которая, скорее всего, будет кэширована в процессоре, и
вы запускаете вещи в довольно жестком цикле и / или процессор может предварительно загрузить данные.
Предпосылки и почему
С точки зрения процессора, ваша память медленная. Чтобы компенсировать разницу в скорости, в ваш процессор встроено несколько кешей (кеш L1 / L2). Итак, представьте, что вы делаете свои красивые вычисления и выясняете, что вам нужен кусок памяти. Процессор выполняет операцию «загрузки» и загружает часть памяти в кеш, а затем использует кеш для выполнения остальных вычислений. Поскольку память относительно медленная, эта «загрузка» замедлит вашу программу.
Как и прогнозирование ветвлений, это было оптимизировано в процессорах Pentium: процессор предсказывает, что ему необходимо загрузить часть данных, и пытается загрузить ее в кеш до того, как операция действительно попадет в кеш. Как мы уже видели, предсказание ветвления иногда ужасно неверно - в худшем случае вам нужно вернуться и фактически дождаться загрузки памяти, которая займет вечность (другими словами: предсказание неудачного ветвления плохое, память нагрузка после неудачного предсказания ветвления просто ужасна!).
К счастью для нас, если модель доступа к памяти предсказуема, процессор загрузит ее в свой быстрый кеш, и все будет хорошо.
Первое, что нам нужно знать, это что такое маленькое? Хотя чем меньше, тем лучше, но, как правило, лучше использовать таблицы поиска размером <= 4096 байт. В качестве верхнего предела: если ваша таблица поиска больше 64 КБ, вероятно, стоит пересмотреть.
Построение стола
Итак, мы выяснили, что можем создать небольшую таблицу. Следующее, что нужно сделать, это создать функцию поиска. Функции поиска обычно представляют собой небольшие функции, которые используют пару основных целочисленных операций (и, или, xor, сдвиг, добавление, удаление и, возможно, умножение). Вы хотите, чтобы введенные вами данные были переведены функцией поиска в какой-то «уникальный ключ» в вашей таблице, который затем просто дает вам ответ на всю работу, которую вы хотели выполнить.
В этом случае:> = 128 означает, что мы можем сохранить значение, <128 означает, что мы избавляемся от него. Самый простой способ сделать это - использовать «И»: если мы сохраним его, мы сделаем И с помощью 7FFFFFFF; если мы хотим избавиться от него, мы И его с 0. Обратите также внимание на то, что 128 - это степень двойки, поэтому мы можем продолжить и составить таблицу из 32768/128 целых чисел и заполнить ее одним нулем и множеством 7FFFFFFFF's.
Управляемые языки
Вы можете задаться вопросом, почему это хорошо работает на управляемых языках. В конце концов, управляемые языки проверяют границы массивов с помощью ветки, чтобы убедиться, что вы не напортачите ...
Ну не совсем ... :-)
Была проделана значительная работа по устранению этой ветки для управляемых языков. Например:
for (int i = 0; i  = 128)? c: 0;
}
// Контрольная работа
DateTime startTime = System.DateTime.Now;
длинная сумма = 0;
для (int i = 0; i <100000; ++ i)
{
// Первичный цикл
для (int j = 0; j  у && z <5.0;
является оптимальным в большинстве случаев (если вы не ожидаете, что выражение && будет генерировать много неверных предсказаний ветвления).
|
Это уж точно!...
Прогнозирование ветвлений замедляет работу логики из-за переключения, которое происходит в вашем коде! Как будто вы идете по прямой улице или по улице с большим количеством поворотов, наверняка прямой будет быстрее! ...
Если массив отсортирован, ваше условие ложно на первом шаге: data [c]> = 128, затем становится истинным значением на всем пути до конца улицы. Так вы быстрее доберетесь до конца логики. С другой стороны, используя несортированный массив, вам нужно много поворачивать и обрабатывать, что наверняка заставит ваш код работать медленнее ...
Посмотрите на изображение, которое я создал для вас ниже. Какая улица будет закончена быстрее?
Таким образом, программно предсказание ветвления замедляет процесс ...
Также, в конце, приятно знать, что у нас есть два типа предсказаний ветвления, каждый из которых по-разному повлияет на ваш код:
1. Статический
2. Динамический
Статическое предсказание ветвлений используется микропроцессором впервые
встречается условный переход, и предсказание динамического перехода
используется для успешного выполнения кода условного перехода.
Чтобы эффективно написать код, чтобы воспользоваться этими
правила, при написании операторов if-else или switch проверяйте наиболее
Сначала распространенные случаи, а затем постепенно уменьшаются до наименее распространенных.
Циклы не обязательно требуют какого-либо специального заказа кода для
статическое предсказание ветвления, так как только условие итератора цикла
обычно используется.
|
На этот вопрос уже много раз давали превосходные ответы. Тем не менее, я хотел бы обратить внимание группы на еще один интересный анализ.
Недавно этот пример (очень немного измененный) также использовался как способ продемонстрировать, как можно профилировать фрагмент кода в самой программе в Windows. Попутно автор также показывает, как использовать результаты, чтобы определить, где код тратит большую часть времени, как в отсортированном, так и в несортированном случае. Наконец, в этой части также показано, как использовать малоизвестную функцию HAL (уровень аппаратной абстракции), чтобы определить, насколько неверно предсказание ветвлений происходит в несортированном случае.
Ссылка здесь:
Демонстрация самопрофилирования
|
Как уже упоминалось другими, за загадкой стоит Branch Predictor.
Я не пытаюсь что-то добавить, но объясняю концепцию по-другому.
В вики есть краткое введение, содержащее текст и диаграммы.
Мне нравится приведенное ниже объяснение, в котором используется диаграмма для интуитивной разработки предсказателя ветвления.
В компьютерной архитектуре предсказателем ветвления является
цифровая схема, которая пытается угадать, в каком направлении ветвь (например,
if-then-else структура) будет работать до того, как это станет известно наверняка. В
цель предсказателя ветвления - улучшить поток в
конвейер команд. Предикторы ветвления играют решающую роль в
достижение высокой эффективности во многих современных конвейерных
микропроцессорные архитектуры, такие как x86.
Двустороннее ветвление обычно реализуется с помощью условного перехода.
инструкция. Условный переход можно «не выполнять» и продолжить.
выполнение с первой ветвью кода, которая следует сразу за
после условного перехода, или его можно "взять" и перейти к
другое место в программной памяти, где находится вторая ветвь кода.
хранится. Доподлинно неизвестно, будет ли условный переход
приняты или не приняты до тех пор, пока условие не будет рассчитано и
условный переход прошел стадию выполнения в инструкции
трубопровод (см. рис. 1).
На основе описанного сценария я написал демонстрацию анимации, чтобы показать, как инструкции выполняются в конвейере в различных ситуациях.
Без предсказателя ветвления.
Без предсказания ветвления процессору пришлось бы ждать, пока
инструкция условного перехода прошла этап выполнения до
следующая инструкция может перейти на этап выборки в конвейере.
Пример содержит три инструкции, первая из которых - инструкция условного перехода. Последние две инструкции могут поступать в конвейер до тех пор, пока не будет выполнена инструкция условного перехода.
Для выполнения 3 инструкций потребуется 9 тактов.
Используйте предсказатель ветвлений и не делайте условных переходов. Предположим, что прогноз не принимаетусловный переход.
Для выполнения 3 инструкций потребуется 7 тактов.
Используйте предсказатель ветвлений и совершите условный переход. Предположим, что прогнозируемый объект не выполняет условный переход.
Для выполнения 3 инструкций потребуется 9 тактов.
Время, которое тратится впустую в случае неверного предсказания перехода, равно
количество этапов в конвейере от этапа выборки до
выполнить этап. Современные микропроцессоры, как правило, имеют довольно длинные
конвейеры, так что задержка неверного предсказания составляет от 10 до 20 часов
циклы. В результате увеличение длины трубопровода увеличивает потребность в
более продвинутый предсказатель ветвлений.
Как видите, похоже, у нас нет причин не использовать Branch Predictor.
Это довольно простая демонстрация, которая разъясняет самую основную часть Branch Predictor. Если эти гифки раздражают, пожалуйста, удалите их из ответа, и посетители также могут получить исходный код живой демонстрации из BranchPredictorDemo.
|
Улучшение предсказания ветвлений!
Важно понимать, что неверное предсказание ветвления не замедляет работу программ. Стоимость пропущенного предсказания такая же, как если бы предсказания ветвления не существовало, и вы ждали, пока оценка выражения решит, какой код запустить (дальнейшее объяснение в следующем абзаце).
если (выражение)
{
// Запуск 1
} else {
// Запуск 2
}
Всякий раз, когда есть оператор if-else \ switch, выражение должно быть вычислено, чтобы определить, какой блок следует выполнить. В ассемблерный код, созданный компилятором, вставляются инструкции условного перехода.
Команда ветвления может заставить компьютер начать выполнение другой последовательности команд и, таким образом, отклониться от своего поведения по умолчанию, заключающегося в выполнении инструкций по порядку (т.е. если выражение ложно, программа пропускает код блока if) в зависимости от некоторого условия, которое - это оценка выражения в нашем случае.
При этом компилятор пытается предсказать результат до того, как он будет фактически оценен. Он получит инструкции из блока if, и если выражение окажется истинным, тогда замечательно! Мы выиграли время, необходимое для его оценки, и добились прогресса в коде; в противном случае мы запускаем неправильный код, конвейер очищается и запускается правильный блок.
Визуализация:
Допустим, вам нужно выбрать маршрут 1 или маршрут 2. Ожидая, пока ваш партнер проверит карту, вы остановились на ## и ждали, или вы можете просто выбрать маршрут 1 и, если вам повезет (маршрут 1 - правильный маршрут), Тогда здорово, что вам не нужно было ждать, пока ваш партнер проверит карту (вы сэкономили время, которое потребовалось бы ему, чтобы проверить карту), иначе вы просто повернете назад.
Хотя промывка трубопроводов происходит очень быстро, в настоящее время риск стоит того. Прогнозирование отсортированных данных или данных, которые изменяются медленно, всегда проще и лучше, чем прогнозирование быстрых изменений.
O Маршрут 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Маршрут 2 \ --------------------------------
|
В ARM нет необходимости в ветвлении, потому что каждая инструкция имеет 4-битное поле условия, которое проверяет (с нулевой стоимостью) любое из 16 различных условий, которые могут возникнуть в регистре состояния процессора, и если условие в инструкции false, инструкция пропускается. Это устраняет необходимость в коротких ветвях, и для этого алгоритма не будет попадания в предсказание ветвления. Следовательно, отсортированная версия этого алгоритма будет работать медленнее, чем несортированная версия на ARM из-за дополнительных накладных расходов на сортировку.
Внутренний цикл этого алгоритма на языке ассемблера ARM будет выглядеть примерно так:
MOV R0, # 0 // R0 = сумма = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = адрес массива данных (поместите эту инструкцию за пределы внешнего цикла)
.inner_loop // метка ветви внутреннего цикла
LDRB R3, [R2, R1] // R3 = data [c]
CMP R3, # 128 // сравнить R3 со 128
ADDGE R0, R0, R3 // если R3> = 128, то sum + = data [c] - ветвление не требуется!
ADD R1, R1, # 1 // c ++
CMP R1, #arraySize // сравнить c с arraySize
BLT inner_loop // Переход к inner_loop, если c  ());
for (unsigned c = 0; c  = 128
сумма = сумма + данные1 (j);
конец
конец
конец
toc;
ExeTimeWithSorting = toc - tic;
Результаты для приведенного выше кода MATLAB следующие:
a: Прошедшее время (без сортировки) = 3479,880861 секунда.
b: Истекшее время (с сортировкой) = 2377,873098 секунд.
Результаты кода C, как в @GManNickG, я получаю:
a: Прошедшее время (без сортировки) = 19,8761 сек.
b: Истекшее время (с сортировкой) = 7,37778 сек.
Исходя из этого, похоже, что MATLAB почти в 175 раз медленнее, чем реализация C без сортировки и в 350 раз медленнее с сортировкой. Другими словами, эффект (предсказания ветвления) составляет 1,46x для реализации MATLAB и 2,7x для реализации C.
|
Предположение других ответов о том, что нужно отсортировать данные, неверно.
Следующий код сортирует не весь массив, а только его 200-элементные сегменты, и поэтому выполняется быстрее всего.
Сортировка только k-элементных секций завершает предварительную обработку за линейное время, O (n), а не за время O (n.log (n)), необходимое для сортировки всего массива.
#include <алгоритм>
#include 
#include 
int main () {
данные int [32768]; const int l = размер данных / размер данных [0];
for (беззнаковый c = 0; c  = 128)
сумма + = данные [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Это также «доказывает», что это не имеет ничего общего с какой-либо алгоритмической проблемой, такой как порядок сортировки, и это действительно предсказание ветвления.
|
Ответ Бьярна Страуструпа на этот вопрос:
Это похоже на вопрос на собеседовании. Это правда? Как бы вы узнали? Ответить на вопросы об эффективности без предварительного измерения - плохая идея, поэтому важно знать, как это делать.
Итак, я попробовал с вектором из миллиона целых чисел и получил:
Уже отсортировано 32995 миллисекунд
В случайном порядке 125944 миллисекунды
Уже отсортировано 18610 миллисекунд
133304 миллисекунды в случайном порядке
Уже отсортировано 17942 миллисекунды
Перетасовка 107858 миллисекунд
Я запускал это несколько раз, чтобы убедиться. Да, феномен реальный. Мой ключевой код был:
void run (vector  & v, const string & label)
{
авто t0 = system_clock :: now ();
sort (v.begin (), v.end ());
авто t1 = system_clock :: now ();
cout << label
<< duration_cast <микросекунды> (t1 - t0) .count ()
<< "миллисекунды \ n";
}
void tst ()
{
вектор  v (1'000'000);
йота (v.begin (), v.end (), 0);
run (v, «уже отсортировано»);
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "перемешано");
}
По крайней мере, такое явление реально с этим компилятором, стандартной библиотекой и настройками оптимизатора. Различные реализации могут давать и дают разные ответы. Фактически, кто-то провел более систематическое исследование (его можно найти при быстром поиске в Интернете), и большинство реализаций демонстрируют этот эффект.
Одна из причин - предсказание ветвления: ключевая операция в алгоритме сортировки - «if (v [i]  = 128. Это означает, что мы можем легко извлечь один бит, который скажет нам, хотим ли мы значение или нет: путем сдвига данные в правые 7 бит, у нас остается 0 бит или 1 бит, и мы хотим добавить значение только тогда, когда у нас есть 1 бит. Назовем этот бит «бит решения».
Используя значение 0/1 бита решения в качестве индекса в массиве, мы можем сделать код, который будет одинаково быстрым независимо от того, отсортированы данные или нет. Наш код всегда будет добавлять значение, но когда бит решения равен 0, мы добавим значение туда, где нас не волнует. Вот код:
// Контрольная работа
clock_t start = часы ();
long long a [] = {0, 0};
длинная длинная сумма;
for (беззнаковый i = 0; i <100000; ++ i)
{
// Первичный цикл
for (беззнаковый c = 0; c > 7);
a [j] + = данные [c];
}
}
double elapsedTime = static_cast  (часы () - начало) / CLOCKS_PER_SEC;
сумма = а [1];
Этот код тратит впустую половину добавлений, но никогда не приводит к ошибке предсказания ветвления. Это намного быстрее для случайных данных, чем версия с фактическим оператором if.
Но в моем тестировании явная таблица поиска была немного быстрее, чем эта, вероятно, потому, что индексация в таблице поиска была немного быстрее, чем сдвиг бит. Это показывает, как мой код настраивает и использует справочную таблицу (в коде невообразимо названную lut для «LookUp Table»). Вот код C ++:
// Объявить, а затем заполнить таблицу поиска
int lut [256];
for (беззнаковый c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Использование таблицы поиска после ее создания
for (беззнаковый i = 0; i <100000; ++ i)
{
// Первичный цикл
for (беззнаковый c = 0; c  значение)
узел = узел-> pLeft;
еще
узел = узел-> pRight;
эта библиотека будет делать что-то вроде:
i = (x <узел-> значение);
узел = узел-> ссылка [я];
Это хорошее решение, и, возможно, оно сработает.
|
Весьма активный вопрос. Заработайте 10 репутации, чтобы ответить на этот вопрос. Требование репутации помогает защитить этот вопрос от спама и отсутствия ответов.
Не тот ответ, который вы ищете? Просмотрите другие вопросы с метками java c ++ performance optimizer branch-prediction или задайте свой вопрос.